import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 1027.最长等差数列
 */
public class Exerciser7 {
    public int longestArithSeqLength(int[] nums) {
        // 优化，使用 HashMap
        // nums[i],i
        Map<Integer,Integer> hash = new HashMap<>();
        hash.put(nums[0],0);//把0 位置的值进行初始化放入到哈希表中

        int n = nums.length;
        // dp[i][j]: 以i位置和j位置的数据结尾的 所有子序列中 最长的等差数列的长度
        // 这里一个数据不能确定 这个数据可以跟在前面的哪个数据的后面，组成等差数列
        // 但是两个数据，就可以根据等差数列的性质就可以知道是否是等差数列
        int[][] dp = new int[n][n];
        // 初始化为2，最低为2个
        for(int i = 0;i < n;i++) {
            Arrays.fill(dp[i],2);
        }

        int ret = 2;
        for(int i = 1;i < n;i++) { // 固定第二个位置的数
            for(int j = i + 1;j < n;j++) { // 在固定第一个位置后，往后面进行遍历第三个位置的数
                // 在固定完 第二、三个数之后，找第一个位置的数
                // 根据 等差数列的性质
                int a = 2*nums[i] - nums[j];
                // 因为我们把i固定了，在i前面进行把数据放入到hash表中，进行判断是否是等差数列，并且的到其最大值
                // 那么这个 a 的值对应的下标就不会超过 i 位置的下标
                if(hash.containsKey(a)) {
                    dp[i][j] = dp[hash.get(a)][i] + 1;
                    ret = Math.max(ret,dp[i][j]);
                }
            }
            // 在判断结束i位置的数据之后，把i位置的数据放入到 hash表中，进行记录数据
            // 以此实现 一遍dp，一遍进行填hash表的操作
            // 这样也可以实现求到的 a值 是离nums[i] 位置的值最近的值，也就是最长的等差数列的长度在i位置下
            hash.put(nums[i],i);
        }
        return ret;
    }
}
